import java.util.ArrayList;
import java.util.List;

class Solution1 {
    List<List<String>> lists = new ArrayList<>();
    char[][] map;
    boolean[] row;
    boolean[] col;
    boolean[] dig1;
    boolean[] dig2;
    int n;
    public List<List<String>> solveNQueens(int _n) {
        n = _n;
        map = new char[n][n];
        row = new boolean[n];
        col = new boolean[n];
        dig1 = new boolean[2*n];
        dig2 = new boolean[2*n];
        for(int i =0 ; i<n;i++) {
            for(int j = 0; j<n; j++) {
                map[i][j] = '.';
            }
        }
        dfs(0);
        return lists;
    }
    public void dfs(int u) {
        if(u == n) {
            List<String> list = new ArrayList<>();
            for(int i = 0;i <n; i++) {
                String s = new String(map[i]);
                list.add(s);
            }
            lists.add(list);
            return ;
        }

        for(int i = 0; i<n; i++) {
            if(check(u,i)) {
                row[u] = col[i] = dig1[u+i] = dig2[i-u+n] = true;
                map[u][i] = 'Q';
                dfs(u+1);
                row[u] = col[i] = dig1[u+i] = dig2[i-u+n] = false;
                map[u][i] = '.';
            }
        }

    }
    public boolean check(int x, int y) {
        if(row[x] || col[y]) return false;
        if(dig1[x+y] || dig2[y-x+n]) return false;
        return true;
    }
}

class Solution2 {
    boolean row[][] = new boolean[9][10]; //行
    boolean col[][] = new boolean[9][10]; //列
    boolean grid[][][] = new boolean[3][3][10];
    public boolean isValidSudoku(char[][] board) {
        for(int i = 0; i<9; i++) {
            for(int j = 0; j<9; j++) {
                if(board[i][j] != '.') {
                    int x = board[i][j] - '0';
                    if(row[i][x] == true) return false;
                    row[i][x] = true;
                    if(col[j][x] == true) return false;
                    col[j][x] = true;
                    if(grid[i/3][j/3][x] == true) return false;
                    grid[i/3][j/3][x] = true;
                }
            }
        }
        return true;
    }
}

class Solution3 {
    boolean row[][] = new boolean[9][10]; //行
    boolean col[][] = new boolean[9][10]; //列
    boolean grid[][][] = new boolean[3][3][10];

    public void solveSudoku(char[][] board) {
        for(int i = 0; i<9; i++) {
            for(int j = 0; j<9; j++) {
                if(board[i][j]!='.') {
                    int x = board[i][j] - '0';
                    row[i][x] = true;
                    col[j][x] = true;
                    grid[i/3][j/3][x] = true;
                }
            }
        }
        dfs(board);
    }

    public boolean dfs(char[][] board) {
        for(int i = 0; i<9; i++) {
            for(int j =0 ; j<9; j++) {
                if(board[i][j] == '.') {
                    boolean t = false;
                    for(int k = 1; k<=9; k++) {
                        if(!row[i][k] && !col[j][k] && !grid[i/3][j/3][k]) {
                            row[i][k] =col[j][k] =grid[i/3][j/3][k] = true;
                            board[i][j] = (char)(k+'0');
                            boolean flag = dfs(board);
                            if(flag == false) {
                                row[i][k] =col[j][k] =grid[i/3][j/3][k] = false;
                                board[i][j] = '.';
                            }else {
                               return true;
                            }
                        }
                    }
                    if(t == false) return false;
                }
            }
        }

        return true;
    }
}


public class Test {
}
